/*
 * TurboBoyerMoore.cpp
 *
 *  Created on: 01-09-2013
 *      Author: Krzychu
 */

#include "TurboBoyerMoore.h"

#include "../Structures/Config.h"

#define MAX(a, b) (a > b) ? a : b
#define MIN(a, b) (a < b) ? a : b

TurboBoyerMoore::TurboBoyerMoore()
{

}

TurboBoyerMoore::~TurboBoyerMoore()
{

}

std::string TurboBoyerMoore::getName()
{
	return "Turbo Boyer Moore";
}

searchResult TurboBoyerMoore::execute(std::string text, std::string pattern)
{
	searchResult result;
	result.iterationsTaken = 0;

	int textSize = text.size();
	int patternSize = pattern.size();

	int bcShift, i, j, shift, u, v, turboShift;

	/* Preprocessing */
	int* bmGs = pre_good_suffix_shift(pattern);
	int* bmBc = pre_bad_character_shift(pattern);

	/* Searching */
	j = u = 0;
	shift = patternSize;
	while (j <= textSize - patternSize)
	{
		result.iterationsTaken++;

		i = patternSize - 1;
		while (i >= 0 && pattern[i] == text[i + j])
		{
			--i;
			if (u != 0 && i == patternSize - 1 - shift)
				i -= u;
		}
		if (i < 0)
		{
			result.positionsFound.push_back(j);
			if (Config::getInstance()->getFindOneOccurence())
			{
				return result;
			}
			shift = bmGs[0];
			u = patternSize - shift;
		}
		else
		{
			v = patternSize - 1 - i;
			turboShift = u - v;
			bcShift = bmBc[text[i + j]] - patternSize + 1 + i;
			shift = MAX(turboShift, bcShift);
			shift = MAX(shift, bmGs[i]);
			if (shift == bmGs[i])
				u = MIN(patternSize - shift, v);
			else
			{
				if (turboShift < bcShift)
					shift = MAX(shift, u + 1);
				u = 0;
			}
		}
		j += shift;
	}

	return result;
}

